package offer;

import java.util.Stack;
import java.util.TreeMap;

public class Offer30 {
    class MinStack {

        private Stack<Integer> stack;
        private TreeMap<Integer, Integer> treeMap;

        /**
         * initialize your data structure here.
         */
        public MinStack() {
            this.stack = new Stack<Integer>();
            this.treeMap = new TreeMap<>();
        }

        public void push(int x) {
            this.stack.push(x);
            this.treeMap.put(x, this.treeMap.getOrDefault(x, 0) + 1);
        }

        public void pop() {
            Integer pop = this.stack.pop();
            if (this.treeMap.get(pop) > 1) {
                this.treeMap.put(pop, this.treeMap.get(pop) - 1);
                return;
            }
            this.treeMap.remove(pop);
        }

        public int top() {
            return this.stack.peek();
        }

        public int min() {
            return treeMap.firstKey();
        }
    }

    // 3 10 2 1
    class Answer {
        Stack<Integer> A, B;
        public Answer() {
            A = new Stack<>();
            B = new Stack<>();
        }
        public void push(int x) {
            A.add(x);
            if(B.empty() || B.peek() >= x)
                B.add(x);
        }
        public void pop() {
            if(A.pop().equals(B.peek()))
                B.pop();
        }
        public int top() {
            return A.peek();
        }
        public int min() {
            return B.peek();
        }
    }
}
